#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define maxsize 300
#define M 1024
struct redtype
{
	int key;
};
struct sqlist
{
	struct redtype r[maxsize];
	int length;
};
struct sqlist L;

int QSort(int low,int high)
{
	int i,ii,l,h,ll,hh,temp;
	if(L.r[low].key>L.r[high].key)
	{
		temp=L.r[low].key;
		L.r[low].key=L.r[high].key;
		L.r[high].key=temp;
	}
	l=low;h=high-1;
	for(i=l+1;i<=h;)
	{
		if(L.r[i].key<L.r[l].key)
		{
			temp=L.r[i].key;
		    L.r[i].key=L.r[l].key;
		    L.r[l].key=temp; 
		    l++;i++;
		}
		else
		{
		    temp=L.r[i].key;
		    L.r[i].key=L.r[h].key;
		    L.r[h].key=temp; 
			h--;	
		}
	}
	ll=l;h=high;l++;
	for(i=h-1;i>=l;)
	{
		if(L.r[i].key>L.r[h].key)
		{
			temp=L.r[i].key;
		    L.r[i].key=L.r[h].key;
		    L.r[h].key=temp; 
			h--;i--;	
		}
		else
		{
			temp=L.r[i].key;
		    L.r[i].key=L.r[l].key;
		    L.r[l].key=temp; 
		    l++;
		}
	}
	hh=h;
	if(ll>2)QSort(1,ll-1);
	if(hh-ll>3)QSort(ll+1,hh-1);
	if(high-hh>1)QSort(hh+1,high);
	return 0;
}
int main()
{
	freopen("data.txt","r",stdin);
	int k,i;
	double star,finish;
   
	printf("please input the number of sequence:");
	scanf("%d",&k);
	L.length=k;
	printf("\nplease input a  disorderly sequence:\n");
	for(i=1;i<=k;i++)
	{
		scanf("%d",&L.r[i].key);
	}	
	star=(double)clock();
	QSort(1,L.length);	
	printf("the result is:\n");
	for(i=1;i<=L.length;i++)
	   printf("%d,",L.r[i].key);
	printf("\n");
	for(i=0;i<M;i++)
	   finish=(double)clock();
	printf("the time is :%.2fms\n",(finish-star));
}
